/**
 * @program: bagproblem
 * @author: JCM
 * @create: 2023-03-24 11:16
 * @description:
 **/
public class LastStoneWeight2 {
    public static void main(String[] args) {
        int[] stones = {31,26,33,21,40};
        lastStoneWeightII(stones);
    }
    public static int lastStoneWeightII(int[] stones) {
        int len = stones.length;
        int sum = 0;
        for(int i : stones) {
            sum += i;
        }
        int target = sum/2;
        int[] dp = new int[target+1];
        for(int i = 0; i < len; i++) {
            for(int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[target];
    }
}
